#pragma once
#include<iostream>
#include<vector>
using namespace std;

//交换元素
template<typename Comparable>
void swap(Comparable& m, Comparable& n)
{
	Comparable t = m;
	m = n;
	n = t;
}

//插入排序
template<typename Comparable>
void insertionSort(vector<Comparable>& a, int left, int right)
{
	for (int i = 1; i < right; i++) {
		int key = a[i];
		int j = i - 1;
		while ((j >= 0) && key < a[j]) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = key;
	}
}

template<typename Comparable>
const Comparable& median3(vector<Comparable>& a, int left, int right)
{
	right--;
	int center = (left + right) / 2;

	if (a[center] < a[left])
		std::swap(a[left], a[center]);
	if (a[right] < a[left])
		std::swap(a[left], a[right]);
	if (a[right] < a[center])
		std::swap(a[center], a[right]);

	std::swap(a[center], a[right - 1]);
	return a[right - 1];
}

template<typename Comparable>
void quicksort(std::vector<Comparable>& a, int left, int right)
{
	if (left + 10 <= right)
	{
		const Comparable& pivot = median3(a, left, right);
		//分治
		int i = left, j = right - 1;
		for (; ;) {
			while (a[++i] < pivot) {}
			while (pivot < a[--j]) {}
			if (i < j)
				std::swap(a[i], a[j]);
			else
				break;
		}

		std::swap(a[i], a[right - 1]);

		//分别递归处理i的左边和右边
		quicksort(a, left, i - 1);
		quicksort(a, i + 1, right);
	}
	else
		insertionSort(a, left, right);//如果数组长度小于10，采用插入排序
}



template <typename Compareble>
void sort(std::vector<Compareble>& a)
{
	int i = 0, j = a.size();
	quicksort(a, i, j);
}